SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Intersection algorithm</title>

</head>

<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">Intersection algorithm</span></span>

</h1>

</header>

<p>The <b>intersection algorithm</b> is an agreement algorithm used to select sources for estimating accurate time from a number of <a href="Noise" title="Noise">noisy</a> time sources. It forms part of the modern <a href="Network_Time_Protocol" title="Network Time Protocol">Network Time Protocol</a>. It is a modified form of <a href="Marzullo's_algorithm" title="Marzullo's algorithm">Marzullo's algorithm</a>.<sup id="cite_ref-:0_1-0" class="reference"><a href="#cite_note-:0-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-2" class="reference"><a href="#cite_note-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup>

</p><p>While Marzullo's algorithm will return the smallest interval consistent with the largest number of sources, the returned interval does not necessarily include the center point (calculated offset) of all the sources in the intersection. The intersection algorithm returns an interval that includes that returned by Marzullo's algorithm but may be larger since it will include the center points. This larger interval allows using additional statistical data to select a point within the interval, reducing the <a href="Jitter" title="Jitter">jitter</a> in repeated execution.

</p>

<div class="mw-heading mw-heading2"><h2 id="Method">Method</h2></div>

<p>Given <i>M</i> intervals of the form <i>c</i> ± <i>r</i> (which means [<i>c</i>−<i>r</i>,<i>c</i>+<i>r</i>]), the algorithm seeks to find an interval with <i>M</i>−<i>f</i> sources. The value <i>f</i> is referred to as the number of falsetickers, those sources which are in error (the actual value is outside the <a href="Confidence_band" class="mw-redirect" title="Confidence band">confidence band</a>). The best estimate is that which assumes the fewest falsetickers, <i>f</i>. The results will be considered valid if <i>f</i> < <i>M</i>/2, otherwise the algorithm will return failure instead of an interval.

</p><p>The intersection algorithm begins by creating a table of tuples <offset, type>. For each interval there are three entries: the lower endpoint, the midpoint and the upper endpoint, labelled with types −1, 0 and +1 respectively. Thus the interval <i>c</i> ± <i>r</i> results in the entries <<i>c</i>−<i>r</i>,−1>, <<i>c</i>,0> and <<i>c</i>+<i>r</i>,+1>. These entries are then sorted by offset.

</p><p>Variables: This algorithm uses <i>f</i> as number of false tickers, <i>endcount</i> and <i>midcount</i> are integers. <i>Lower</i> and <i>upper</i> are values of offsets.

</p>

<li> [initialize best f] Start with <i>f</i>=0, assuming all input intervals are valid. Each time no interval is found f will be incremented until either an interval is found or <i>f</i> ≥ <i>M</i>/2.</li>

<li> [initialize] <i>endcount</i>=0 and <i>midcount</i>=0.</li>

<li> [find lower endpoint] Start at beginning of the list (lowest offset) consider each tuple in order. <i>endcount</i> = <i>endcount</i>−<i>type</i>. If <i>endcount</i> ≥ <i>M</i>−<i>f</i> then <i>lower</i> = <i>offset</i> and goto step 3 because the (possible) lower endpoint has been found. If the <i>type</i> = 0 then <i>midcount</i> = <i>midcount</i>+1. Repeat with next tuple. If reach end of list then goto step 6.</li>

<li> [tentative lower endpoint found, initialize to find upper endpoint] set <i>endcount</i>=0. </li>

<li> [determine number of midpoints] Start from end of list and work towards lower offsets. <i>endcount</i> = <i>endcount</i>+<i>type</i>. If <i>endcount</i> ≥ <i>M</i>−<i>f</i> then <i>upper</i> = <i>offset</i>, goto step 5. If <i>type</i> = 0 then <i>midcount</i> = <i>midcount</i>+1. Repeat for next tuple. If reach end of list then goto step 6.</li>

<li> if <i>lower</i> ≤ <i>upper</i> and <i>midcount</i> ≤ <i>f</i> then return interval [<i>lowerendpoint</i>, <i>upperendpoint</i>] as resulting confidence interval.</li>

<li>[increment number of falsetickers] <i>f</i> = <i>f</i>+1. If <i>f</i> ≥ <i>M</i>/2 then terminate and return FAILED, otherwise goto step 1.</li>

</ol>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFMills2013" class="citation journal cs1">Mills, D. (2013). <a rel="nofollow" class="external text" href="http://tools.ietf.org/html/rfc1305#ref-DEC89">"RFC 1305 - Network Time Protocol (Version 3) Specification, Implementation and Analysis"</a>. <i>tools.ietf.org</i>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.17487%2FRFC1305">10.17487/RFC1305</a></span><span class="reference-accessdate">. Retrieved <span class="nowrap">October 6,</span> 2013</span>. <q>Digital Time Service Functional Specification Version T.1.0.5. Digital Equipment Corporation, 1989.</q></cite></span>

</li>

<li id="cite_note-2"><span class="mw-cite-backlink"><b><a href="#cite_ref-2">^</a></b></span> <span class="reference-text">Digital Time Service Functional Specification Version T.1.0.5. Digital

Equipment Corporation, 1989.</span>

</li>

</ol></div></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-03-29" href="https://en.wikipedia.org/wiki/?title=Intersection_algorithm&oldid=1282972497">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>